/*
 * Copyright (c) 2022  by Junzhao
 * THIS FILE IS PART OF JAVA-Data-Structures-and-Algorithms PROJECT
 * All Rights Reserved.
 */

package 线索二叉树;


/**
 * @Description 线索二叉树
 * 在二叉树的结点上加上线索的二叉树称为线索二叉树，
 * 对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，
 * 使其变为线索二叉树的过程称为对二叉树进行线索化。
 * <p>
 * 对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，
 * 利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，
 * 这些指针称为线索，加上线索的二叉树称为线索二叉树。
 * <p>
 * 这种加上了线索的二叉链表称为线索链表，
 * 相应的二叉树称为线索二叉树(Threaded BinaryTree)。
 * 根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
 * 一个结点的前一个结点，称为前驱结点
 * 一个结点的后一个结点，称为后继结点（前后区别由遍历方式决定）
 * <p>
 * 注意：线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题，
 * 解决了二叉链表找左、右孩子困难的问题。
 * @Author 俊昭
 * @Date 2022/5/5
 */
public class ThreadedBinaryTree {
    // 构造一个二叉树
    private static Node root = new Node(1);
    private static Node pre = null;// 前驱节点


    static {// 手动创建 暂时
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
//        root.left.left.left = new Node(8,"呼延灼");
//        root.left.left.right = new Node(9,"花荣");
    }

    /**
     * @description 前序
     * @author 俊昭
     * @date 2022/5/6
     */
    public static void preThreaded() {
        preThreaded(root);
    }

    /**
     * @param node 开始进行线索化的根节点
     * @description 前序线索化
     * @author 俊昭
     * @date 2022/5/6
     */
    private static void preThreaded(Node node) {
        if (node == null) {
            return;
        }

        if (node.left == null) {
            // 左节点为空 将此节点的左子节点为前驱节点
            node.left = pre;
            node.leftType = 1;
        }

        if (pre != null && pre.right == null && pre.left != node) {
            // 右节点为空 前驱节点不空 此将节点为pre的后继节点
            pre.right = node;
            pre.rightType = 1;
        }
        // 此节点为前驱节点
        pre = node;
        if (pre.leftType == 0) {
            preThreaded(node.left);
        }
        if (pre.leftType == 0) {
            preThreaded(node.right);
        }
    }

    /**
     * @description 前序遍历 线索化前序二叉树
     * @author 俊昭
     * @date 2022/5/6
     */
    public static void preThreadList() {
        preThreadList(root);
    }

    private static void preThreadList(Node node) {
        if (node == null) {
            return;
        }
        if (node.leftType == 1 || node.rightType == 1) {
            System.out.println(node);
            return;
        }
        System.out.println(node);
        preThreadList(node.left);
        preThreadList(node.right);
    }

    /**
     * @description 中序
     * @author 俊昭
     * @date 2022/5/6
     */
    public static void midThreaded() {
        midThreaded(root);
    }

    /**
     * @param node 开始进行线索化的根节点
     * @description 中序线索化
     * @author 俊昭
     * @date 2022/5/6
     */
    private static void midThreaded(Node node) {
        if (node == null) {
            return;
        }
        midThreaded(node.left);

        if (node.left == null) {
            // 左节点为空 将此节点的左子节点为前驱节点
            node.left = pre;
            node.leftType = 1;
        }

        if (pre != null && pre.right == null) {
            // 右节点为空 前驱节点不空 此将节点为pre的后继节点
            pre.right = node;
            pre.rightType = 1;
        }
        // 此节点为前驱节点
        pre = node;
        midThreaded(node.right);
    }

    /**
     * @description 中序遍历 线索化中序二叉树
     * @author 俊昭
     * @date 2022/5/6
     */
    public static void midThreadList() {
        midThreadList(root);
//        Node node = root;
//        while (node != null) {
//            while (node.leftType == 0) {
//                node = node.left;
//            }
//            System.out.println(node);
//            while (node.rightType == 1) {
//                node = node.right;
//                System.out.println(node);
//            }
//            node = node.right;
//        }
    }

    private static void midThreadList(Node node) {
        if (node == null) {
            return;
        }
        if (node.rightType == 1) {
            System.out.println(node);
            return;
        }
        midThreadList(node.left);
        System.out.println(node);
        midThreadList(node.right);

    }


    /**
     * @description 后序
     * @author 俊昭
     * @date 2022/5/6
     */
    public static void postThreaded() {
        postThreaded(root);
    }

    /**
     * @param node 开始进行线索化的根节点
     * @description 后序线索化
     * @author 俊昭
     * @date 2022/5/6
     */
    private static void postThreaded(Node node) {
        if (node == null) {
            return;
        }
        if (pre != null && pre.leftType == 0) {
            postThreaded(node.left);
        }
        if (pre != null && pre.rightType == 0) {
            postThreaded(node.right);
        }

        if (node.left == null) {
            // 左节点为空 将此节点的左子节点为前驱节点
            node.left = pre;
            node.leftType = 1;
        }

        if (pre != null && pre.right == null) {
            // 右节点为空 前驱节点不空 此将节点为pre的后继节点
            pre.right = node;
            pre.rightType = 1;
        }
        // 此节点为前驱节点
        pre = node;
    }

    /**
     * @description 后序遍历 线索化后序二叉树
     * @author 俊昭
     * @date 2022/5/6
     */
    public static void postThreadList() {
        postThreadList(root);
    }

    private static void postThreadList(Node node) {
        if (node == null || node.rightType == 1) {
            if (node != null) {
                System.out.println(node);
            }
            return;
        }
        postThreadList(node.left);
        postThreadList(node.right);
        System.out.println(node);
    }

}

class Node {
    Node left;
    Node right;
    //如果为0，表示左子树；如果为1，表示前驱节点
    int leftType;
    //如果为0，表示右子树；如果为1，表示后继节点
    int rightType;
    private final int no;

    public Node(int no) {
        this.no = no;
    }

    @Override
    public String toString() {
        return "Node{ " + no +
                " }";
    }
}

